# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
# 
#  有效字符串需满足： 
# 
#  
#  左括号必须用相同类型的右括号闭合。 
#  左括号必须以正确的顺序闭合。 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "()"
# 输出：true
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "()[]{}"
# 输出：true
#  
# 
#  示例 3： 
# 
#  
# 输入：s = "(]"
# 输出：false
#  
# 
#  示例 4： 
# 
#  
# 输入：s = "([)]"
# 输出：false
#  
# 
#  示例 5： 
# 
#  
# 输入：s = "{[]}"
# 输出：true 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 104 
#  s 仅由括号 '()[]{}' 组成 
#  
#  Related Topics 栈 字符串 
#  👍 2347 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        d = {
            ')': '(',
            ']': '[',
            '}': '{',
        }
        stack = []
        for ch in s:
            if ch not in d:
                stack.append(ch)
            else:
                if not stack or stack[-1] != d[ch]:
                    return False
                else:
                    stack.pop()
        return not stack



# leetcode submit region end(Prohibit modification and deletion)


# 解法: 栈 后遇到的先闭合
# def isValid(self, s: str) -> bool:
#     if len(s) % 2 == 1:
#         return False
#     d = {
#         ')': '(',
#         ']': '[',
#         '}': '{'
#     }
#     stack = []
#     for ch in s:
#         if ch not in d:
#             stack.append(ch)
#         else:
#             if not stack or d[ch] != stack[-1]:
#                 return False
#             else:
#                 stack.pop()
#     return not stack
# stack isEmpty not stack
# stack isNotEmpty stack
def log(*args, **kwargs):
    print(*args, **kwargs)


if __name__ == '__main__':
    sol = Solution()
    assert sol.isValid('()[]{}')
    assert not sol.isValid('([)]')
    sol.isValid('){')
